//快排 typescript
function quickSort(arr: number[]) : number[] {
    if (arr.length <= 1) {
        return arr;
    }
    const pivot = arr[0];
    const left = [];
    const right = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {//小于pivot的放在左边
            left.push(arr[i]);//放入左边
        } else {            //大于pivot的放在右边
            right.push(arr[i]);
        }
    }
    return [...quickSort(left), pivot, ...quickSort(right)];//递归    左边排好序，右边排好序
}

function singleNumber(arr1: number[]): number {
    let arr = quickSort(arr1);
    for (let i = 0; 2*i < arr.length; i++) {
        if(arr[2*i] !== arr[2*i+1]){
            return arr[2*i];
        }
    }
    return arr[arr.length-1];
}
// function singleNumber(nums: number[]): number {
//     return nums.reduce((pre, cur) => pre ^ cur);
// };

let arr = quickSort([4,1,2,1,2])
console.log(arr);


console.log(singleNumber(arr));